<?php
/**
 * @title 1976. 到达目的地的方案数
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }

class Solution {

    /**
     * @param Integer $n
     * @param Integer[][] $roads
     * @return Integer
     */
    function countPaths($n, $roads) {
        /**
         * @since 2024-03-05 请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 10^9 + 7 取余 后返回。
         */
        $pathCount = 0;
        $minTime = PHP_INT_MAX;

        /**
         * @since 2024-03-05 遍历roads，生成点到点的路径和时间
         */
        $hash = [];
        foreach ($roads as list($s, $e, $t)){
            $hash[$s][$e] = [$e, $t];
            $hash[$e][$s] = [$s, $t];
        }

        /**
         * @since 2024-03-05 达到每个点的最短时间
         */
        $timeArray = [0=>0];

        /**
         * @since 2024-03-05 BFS广度遍历
         */
        $nodeArray = [
            [0, 1],
        ];
        while($nodeArray){
            /**
             * @since 2024-03-05 下次遍历元素的集合
             */
            $nextNodeArray = [];

            /**
             * @since 2024-03-05 遍历当前元素集合
             */
            foreach ($nodeArray as list($node, $cnt)){
                echo "[{$node}, {$cnt}],";

                /**
                 * @since 2024-03-05 下次遍历的元素
                 */
                foreach ($hash[$node] as list($nextNode, $nextTime)){
                    $t = $timeArray[$node] + $nextTime;

                    /**
                     * @since 2024-03-05 到达终点
                     */
                    if($nextNode == $n-1){
                        if($minTime > $t){
                            $minTime = $t;
                            $pathCount = $cnt;
                        } elseif($minTime == $t){
                            $pathCount += $cnt;
                        } else {}
                    } else {
                        /**
                         * @since 2024-03-05 时间是否更短
                         */
                        if(!isset($timeArray[$nextNode]) OR $t < $timeArray[$nextNode]){
                            $timeArray[$nextNode] = $t;
                            if($t < $minTime){
                                $nextNodeArray[$nextNode] = [$nextNode, $cnt];
                            } else {}
                        } elseif($t == $timeArray[$nextNode]) {
                            if($t < $minTime){
                                if(isset($nextNodeArray[$nextNode])){
                                    $nextNodeArray[$nextNode][1] += $cnt;
                                } else {
                                    $nextNodeArray[$nextNode] = [$nextNode, $cnt];
                                }
                            } else {}
                        } else {}
                    }
                }
            }
            echo str_repeat(PHP_EOL, 2);

            /**
             * @since 2024-03-05 下次遍历
             */
            $nodeArray = $nextNodeArray;
        }

        /**
         * @return
         */
        return $pathCount % (pow(10,9)+7);
    }
}


/**
 * @url http://127.0.0.1/leetcode/202403/2024.03.05.php
 */
$datas = [
    // [7, [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]], // 4
    [22, [[1,0,1983],[1,2,4922],[2,3,3643],[2,4,9994],[1,4,14916],[4,0,16899],[5,4,4354],[0,5,21253],[2,6,15836],[6,1,20758],[6,0,22741],[6,3,12193],[6,5,1488],[4,6,5842],[7,0,18855],[7,1,16872],[7,3,8307],[8,7,9446],[4,8,11402],[3,8,17753],[8,6,5560],[4,9,13109],[6,9,7267],[8,9,1707],[3,9,19460],[9,7,11153],[0,9,30008],[9,5,8755],[9,1,28025],[9,2,23103],[5,10,13248],[3,10,23953],[1,10,32518],[7,10,15646],[9,10,4493],[11,9,7385],[12,3,36592],[12,5,25887],[7,12,28285],[12,11,9747],[12,6,24399],[2,12,40235],[13,8,18968],[4,13,30370],[13,0,47269],[13,2,40364],[5,13,26016],[13,9,17261],[11,13,9876],[13,3,36721],[1,13,45286],[7,13,28414],[10,13,12768],[2,14,48419],[14,1,53341],[12,14,8184],[14,11,17931],[14,9,25316],[15,0,62624],[9,15,32616],[15,14,7300],[13,15,15355],[15,2,55719],[16,5,31585],[13,16,5569],[0,16,52838],[12,16,5698],[16,9,22830],[16,10,18337],[16,11,15445],[1,16,50855],[6,16,30097],[16,7,33983],[16,17,6677],[17,1,57532],[14,17,4191],[17,8,31214],[0,17,59515],[18,14,1723],[12,18,9907],[0,18,57047],[5,18,35794],[16,18,4209],[10,18,22546],[18,3,46499],[19,7,10407],[19,8,961],[6,20,38441],[2,20,54277],[11,20,23789],[20,12,14042],[20,1,59199],[14,20,5858],[2,21,55541],[21,18,5399],[21,1,60463]]], // 665
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    /**
     * @since 2024-01-15 超时和错误案例参数
     */
    // $data = $xhprof->FormatArgs("/tmp/leetcode/xxx-xxx.txt");

    // $data[0] = $xhprof->listNode($data[0]);
    // $data[0] = $xhprof->tree($data[0]);
    echo $xhprof->DumpArgs($data);
    echo "\n<hr>\n";

    $obj = new Solution();
    $result = $obj->countPaths(...$data);
    echo $xhprof->DumpArgs([$result]);
    var_dump($result);

    echo "\n<hr>". str_repeat("<br>", 2) . str_repeat(PHP_EOL, 5);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
